//
// Created by mac on 2023/11/7.
//

// 零钱兑换
class Solution
{
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount)
    {
        // 1、建表
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        // 2、初始化
        for(int j = 1; j <= amount; ++j) dp[0][j] = INF;
        // 3、填表
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j <= amount; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i-1] && dp[i][j - coins[i-1]] != INF) dp[i][j] = min(dp[i][j], dp[i][j - coins[i-1]] + 1);
            }
        // 4、返回值
        return dp[n][amount] == INF ? -1 : dp[n][amount];
    }
};
/*
- 时间复杂度：O(n * amount)
- 空间复杂度：O(n * amount)
*/

// -----------------------------------------------------------

// 优化版本
// 1、删除 dp 中的横坐标
// 2、纵坐标从左往右的顺序遍历
class Solution
{
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount)
    {
        // 1、建表
        int n = coins.size();
        vector<int> dp(amount + 1, INF);
        // 2、初始化
        dp[0] = 0;
        // 3、填表
        for(int i = 1; i <= n; ++i)
            for(int j = coins[i-1]; j <= amount; ++j)
                dp[j] = min(dp[j], dp[j - coins[i-1]] + 1);
        // 4、返回值
        return dp[amount] == INF ? -1 : dp[amount];
    }
};
/*
- 时间复杂度：O(n * amount)
- 空间复杂度：O(amount)
*/

// 零钱兑换
// 未优化版本
class Solution
{
public:
    int change(int amount, vector<int>& coins)
    {
        // 1、建表
        int n = coins.size();
        vector< vector<int> > dp(n + 1, vector<int>(amount + 1));
        // 2、初始化
        dp[0][0] = 1;
        // 3、填表
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j <= amount; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
            }
        // 4、返回值
        return dp[n][amount];
    }
};
/*
- 时间复杂度：O(n * amount)
- 空间复杂度：O(n * amount)
*/

// -----------------------------------------------------------------------------

// 利用滚动数组进行空间优化
// 1、删除 dp 表的横坐标
// 2、纵坐标从左往右遍历
class Solution
{
public:
    int change(int amount, vector<int>& coins)
    {
        // 1、建表
        int n = coins.size();
        vector<int> dp(amount + 1);
        // 2、初始化
        dp[0] = 1;
        // 3、填表
        for(const auto e : coins)
            for(int j = e; j <= amount; ++j)
                dp[j] += dp[j - e];
        // 4、返回值
        return dp[amount];
    }
};
/*
- 时间复杂度：O(n * amount)
- 空间复杂度：O(amount)
*/

// 零钱兑换II
// 未优化版本
class Solution
{
public:
    int change(int amount, vector<int>& coins)
    {
        // 1、建表
        int n = coins.size();
        vector< vector<int> > dp(n + 1, vector<int>(amount + 1));
        // 2、初始化
        dp[0][0] = 1;
        // 3、填表
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j <= amount; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
            }
        // 4、返回值
        return dp[n][amount];
    }
};
/*
- 时间复杂度：O(n * amount)
- 空间复杂度：O(n * amount)
*/

// -----------------------------------------------------------------------------

// 利用滚动数组进行空间优化
// 1、删除 dp 表的横坐标
// 2、纵坐标从左往右遍历
class Solution
{
public:
    int change(int amount, vector<int>& coins)
    {
        // 1、建表
        int n = coins.size();
        vector<int> dp(amount + 1);
        // 2、初始化
        dp[0] = 1;
        // 3、填表
        for(const auto e : coins)
            for(int j = e; j <= amount; ++j)
                dp[j] += dp[j - e];
        // 4、返回值
        return dp[amount];
    }
};
/*
- 时间复杂度：O(n * amount)
- 空间复杂度：O(amount)
*/

// 完全平方数
// // 未优化版本
// class Solution
// {
// public:
//     const int INF = 0x3f3f3f3f;

//     int numSquares(int n)
//     {
//         // 1、建表
//         int m = sqrt(n);
//         vector< vector<int> > dp(m + 1, vector<int>(n + 1));
//         // 2、初始化
//         for(int j = 1; j <= n; ++j) dp[0][j] = INF;
//         // 3、填表
//         for(int i = 1; i <= m; ++i)
//             for(int j = 0; j <= n; ++j)
//             {
//                 dp[i][j] = dp[i - 1][j];
//                 if(j >= i*i && dp[i][j - i*i] != INF) dp[i][j] = min(dp[i][j], dp[i][j - i*i] + 1);
//             }
//         // 4、返回值
//         return dp[m][n];
//     }
// };
// /*
// - 时间复杂度：O(n^2)
// - 空间复杂度：O(n^2)
// */

// ------------------------------------------------------

// 利用滚动数组进行空间优化
// 1、删除 dp 表的横坐标
// 2、纵坐标从左往右遍历
class Solution
{
public:
    const int INF = 0x3f3f3f3f;

    int numSquares(int n)
    {
        // 1、建表
        int m = sqrt(n);
        vector<int> dp(n + 1, INF);
        // 2、初始化
        dp[0] = 0;
        // 3、填表
        for(int i = 1; i <= m; ++i)
            for(int j = i*i; j <= n; ++j)
                dp[j] = min(dp[j], dp[j - i*i] + 1);
        // 4、返回值
        return dp[n];
    }
};
/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
*/

// 一和零
// 未优化版本
class Solution
{
public:
    int findMaxForm(vector<string>& strs, int m, int n)
    {
        // 1、建表 && 初始化
        int len = strs.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));

        // 2、填表
        for(int i = 1; i <= len; ++i)
        {
            // 计算 strs[i] 中，'0' 和 '1' 的个数
            int a = 0, b = 0;
            for(const auto e : strs[i - 1])
            {
                if(e == '0') ++a;
                else ++b;
            }
            // 继续遍历其它维度
            for(int j = 0; j <= m; ++j)
                for(int k = 0; k <= n; ++k)
                {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= a && k >= b) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-a][k-b] + 1);
                }
        }
        // 3、返回值
        return dp[len][m][n];
    }
};
/*
- 时间复杂度：O(len * m * n)
- 空间复杂度：O(len * m * n)
*/

// ----------------------------

// 利用滚动数组进行空间优化
// 1、删除 dp 表的横坐标
// 2、修改 j 和 k 维度的遍历顺序（改为从大到小）
class Solution
{
public:
    int findMaxForm(vector<string>& strs, int m, int n)
    {
        // 1、建表 && 初始化
        int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // 2、填表
        for(int i = 0; i < len; ++i)
        {
            // 计算 strs[i] 中，'0' 和 '1' 的个数
            int a = 0, b = 0;
            for(const auto e : strs[i])
            {
                if(e == '0') ++a;
                else ++b;
            }
            // 继续遍历其它维度
            for(int j = m; j >= a; --j)
                for(int k = n; k >= b; --k)
                    dp[j][k] = max(dp[j][k], dp[j-a][k-b] + 1);
        }
        // 3、返回值
        return dp[m][n];
    }
};
/*
- 时间复杂度：O(len * m * n)
- 空间复杂度：O(len * m * n)
*/

// 盈利计划
// 未优化版本
class Solution
{
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
    {
        // 1、建表
        int len = group.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        // 2、初始化
        for(int j = 0; j <= n; ++j) dp[0][j][0] = 1;
        // 3、填表
        for(int i = 1; i <= len; ++i)
            for(int j = 0; j <= n; ++j)
                for(int k = 0; k <= minProfit; ++k)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j >= group[i - 1]) dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= (int)(1e9 + 7);
                }
        // 4、返回值
        return dp[len][n][minProfit];
    }
};
/*
- 时间复杂度：O(len * n * profit)
- 空间复杂度：O(len * n * profit)
*/

// ---------------------

// 利用滚动数组进行空间优化
// 1、删除 dp 表的横坐标
// 2、修改 j 和 k 维度的遍历顺序（改为从大到小）
class Solution
{
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
    {
        int len = group.size();
        // 1、建表
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for(int j = 0; j <= n; ++j) dp[j][0] = 1;
        // 2、填表
        for(int i = 0; i < len; ++i)
            for(int j = n; j >= group[i]; --j)
                for(int k = minProfit; k >= 0; --k)
                {
                    dp[j][k] += dp[j - group[i]][max(0, k - profit[i])];
                    dp[j][k] %= (int)(1e9 + 7);
                }
        // 3、返回值
        return dp[n][minProfit];
    }
};
/*
- 时间复杂度：O(len * n * profit)
- 空间复杂度：O(n * profit)
*/

 // 组合总数IV
 class Solution
 {
 public:
     int combinationSum4(vector<int>& nums, int target)
     {
         // 1、建表
         vector<double> dp(target + 1);
         // 2、初始化
         dp[0] = 1;
         // 3、填表
         for(int i = 1; i <= target; ++i)
             for(int j = 0; j < nums.size(); ++j)
                 if(i >= nums[j]) dp[i] += dp[i - nums[j]];
         // 4、返回值
         return dp[target];
     }
 };
/*
- 时间复杂度：O(target * nums.szie())
- 空间复杂度：O(target * nums.szie())
*/

// 不同的二叉搜索树
class Solution
{
public:
    int numTrees(int n)
    {
        // 1、建表
        vector<int> dp(n + 1);
        // 2、初始化
        dp[0] = 1;
        // 3、填表
        for(int i = 1; i <= n; ++i) // i 代表节点数量
            for(int j = 1; j <= i; ++j)// j 代表根节点
                dp[i] += dp[j-1] * dp[i-j];
        // 4、返回值
        return dp[n];
    }
};
/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
*/
